﻿//https://leetcode.cn/problems/decode-string/

class Solution
{
	public :
	string decodeString(string s)
	{
		stack<int> nums;
		stack<string> st;
		st.push("");
		int i = 0, n = s.size();
		while (i < n)
		{
			if (s[i] >= '0' && s[i] <= '9')
			{
				int tmp = 0;
				while (s[i] >= '0' && s[i] <= '9')
				{
					tmp = tmp * 10 + (s[i] - '0');
					i++;
				} 
				nums.push(tmp);
			} 
			else if (s[i] == '[')
			{
				i++; // 把括号后⾯的字符串提取出来
				string tmp = "";
				while (s[i] >= 'a' && s[i] <= 'z')
				{
					tmp += s[i];
					i++;
				} 
				st.push(tmp);
			} 
			else if (s[i] == ']')
			{
				string tmp = st.top();
				st.pop();
				int k = nums.top();
				nums.pop();
				while (k--)
				{
					st.top() += tmp;
				} 
				i++; // 跳过这个右括号
			} 
			else
			{
				string tmp;
				while (i < n && s[i] >= 'a' && s[i] <= 'z')
				{
					tmp += s[i];
					i++;
				} 
				st.top() += tmp;
			}
		} 
		return st.top();
	}
};